package leetcode.editor.cn;
//Java: 反转字符串中的单词
public class ReverseWordsInAString{
    public static void main(String[] args){
      Solution solution=new ReverseWordsInAString().new Solution();
    }
 //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String reverseWords(String s) {
        //1、去除首尾已经中间多余的空格
        StringBuilder sb =removeSpace(s);

        //2、反转整个字符串
        reverseString(sb,0,sb.length()-1);

        //3、反转各个单词
        reverseEachWords(sb);
        return sb.toString();
    }

     private void reverseEachWords(StringBuilder sb) {
         int start = 0;
         int end = 1;
         int n = sb.length();
         while (start < n) {
             while (end < n && sb.charAt(end) != ' ') {
                 end++;
             }
             reverseString(sb, start, end - 1);
             start = end + 1;
             end = start + 1;
         }
     }

     private void reverseString(StringBuilder sb, int start, int end) {
         while (start <= end) {
             char temp = sb.charAt(start);
             sb.setCharAt(start, sb.charAt(end));
             sb.setCharAt(end, temp);
             start++;
             end--;
         }
     }

     private StringBuilder removeSpace(String s) {
         int start = 0;
         int end = s.length() - 1;
         while (s.charAt(start) == ' ') start++;
         while (s.charAt(end) == ' ') end--;
         StringBuilder sb = new StringBuilder();
         while (start <= end) {
             char c = s.charAt(start);
             if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                 sb.append(c);
             }
             start++;
         }
         return sb;
     }
 }
//leetcode submit region end(Prohibit modification and deletion)

}